Packet-switched networks are of increasing interest for the communication of computer data and a variety of other signals. In particular, it seems that Asynchronous Transfer Mode (ATM) networks will be widely employed in the future.
ATM is a packet-oriented switching and multiplexing technique for present and future broadband communication services having a wide spectrum of traffic statistics and Quality of Service (QoS) requirements. ATM offers high bit rates and higher flexibility than Synchronous Transfer Mode (STM). Through statistical multiplexing of many individual connections onto the same link. ATM networks achieve a higher utilization of the network. On the other hand, ATM networks demand more sophisticated connection admission control algorithms and congestion control methods in order to achieve the goal of a statistical multiplexing gain but still fulfilling QoS requirements.
Managing bandwidth in a network can be done in several different ways. In the following, a few approaches are presented.
(a) Peak Rate Allocation
For this method, the user specifies at connection setup only its peak rate. The network then reserves along the path on each link the requested peak bandwidth. The call is rejected if the sum of allocated bandwidths on one involved line exceeds its total capacity. The network reserves this peak rate independent of the user's actual traffic. The network monitors the peak rate of the user and polices its behavior. In case the user exceeds its negotiated peak rate, the network can take corrective actions. This method offers a high guarantee for quality of performance but it leads of course to a poor utilization of the network.
(b) Minimum Bandwidth Allocation
In this approach, the network user specifies the minimal required bandwidth that is needed for the connection. The network then reserves this amount of bandwidth on each link. A new connection is rejected if the total amount of allocated minimal bandwidth on a link would exceed the total link capacity. This method can lead to very high network utilization but a high quality of performance is not guaranteed, especially for sources with great variance in their traffic rates.
(c) Traffic Behavior Specification and Allocation
With this method, the user supplies a whole vector of parameters describing its behavior. In ATM, the vector includes peak cell rate, mean cell rate and maximum burst size. The networK then tries to calculate the needed network resources for the given parameter vector. The decision to accept or refuse a connection is difficult to make in order to achieve high network utilization. There is a trade-off between performance guarantee to the user and network utilization. The statistical multiplexing of several virtual channel connections onto the same link by reserving a bandwidth below the specified peak rate can lead to overbooking of links and therefore to congestion and cell losses. The transformation of the traffic descriptor vector into an amount of bandwidth is a key point to achieve a high network utilization.
The control functions for maintaining the required quality of service and for avoiding congestion in a high-speed packed switched network are either preventive or reactive. A preventive method is the Connection Admission Control (CAC) for new connections, reactive methods are bandwidth adaptation or transmission rate control for already existing connections (established virtual circuits).
In Connection Admission Control (also sometimes termed call admission control), a user has to make a request prior to establishment of a new connection. The respective network unit (such as a link access unit) then makes, based on the declared capacity or bandwidth which the new connection requires and on already existing bandwidth obligations, whether the new connection can be accepted. If not, the request is rejected; otherwise, sufficient bandwidth is allocated for the new connection which is then established.
Several descriptions of CAC methods are available in the prior art among which the following are of particular interest in connection with the present invention:
(a1) German Patent DE 4 134 476 (1993) entitled "Verfahren zur Steuerung der Zulassung von neuen Verbindungen bei asynchronen Zeitmultiplex-Paket-Vermittlungssystemen (Method of Admission Control for New Connections in Asynchronous Time Multiplex Packet Switching Systems)". PA0 (a2) H. Kroener et al.: "Performance Modelling of an Adaptive CAC Strategy for ATM Networks", RACE Project 2068 LACE, 1993. PA0 (a3) U.S. Pat. No. 5,132,966 (1992) entitled "Call Control with Transmission Priority in a Packet Communication Network of an ATM Type". In the system disclosed in this patent, information sources are classified into at least two priorities. A specific bandwidth is assigned to each requesting source which is the specified peak rate for first priority sources and the specified average rate for second priority sources. A request is only accepted if the sum of the bandwidth currently assigned to all accepted sources plus the specific bandwidth of the new source does not exceed the transmission line capacity (predetermined capacity). In this system, the decision is always based on the accumulated sum of requested (reserved) capacities. This does not reflect the actual traffic situation and therefore may often lead to non-optimal utilization of the link. PA0 (a4) H. Saito et al.: "Dynamic Call Admission Control in ATM Networks", IEEE Journal on SAC, Vol.9, No.7 (Sept. 1991), pp.982-989. In this control method, an estimate of cell loss probability is made when a new connection request arrives. The estimate is based on count values of arriving cells and on an estimated traffic characteristic of the new connection, based on parameters specified by the user. A new connection is only accepted if the estimated cell loss probability is below a predetermined value. The method is suited essentially for a single connection only, requires complicated calculations for the cell loss probability, and does not consider the influence of the ratio between fast and slow variations in the traffic rate. PA0 (b1) S.-Q. Li et al.: "Link Capacity Allocation and Network Control by Filtered Input Rate in High-Speed Networks", IEEE/ACM Trans. on Networking, Vol.3, No.1 (Feb.1993), pp. 10-25. The method disclosed in this paper concerns link capacity allocation for a finite buffer system. The allocated link capacity is adaptively changed using an on-line observation of the filtered input rate. The peak input rate for the link is filtered at a properly selected cut-off frequency and only the low-frequency component is considered for the capacity allocation. Though this method eliminates the higher frequency contents of the traffic behavior to achieve an improvement, it is not optimal because the cut off-frequency is fixed once it has been selected so that it does not reflect the possible variations in the distribution between fast and slow changes in the traffic rate. PA0 (b2) U.S. Pat. No. 5,359,593 (1994) entitled "Dynamic Bandwidth Estimation and Adaptation for Packet Communications Networks". This patent discloses a technique for adaptively adjusting the bandwidth allocated to a source, by measuring the mean bit rate of signals from the source and filtering said mean bit rate measurements (and further by measuring and filtering loss probability), and changing the allocated bandwidth when the measured/filtered values are not within given limits. The filtering is done for determining the actual mean bit rate of the incoming traffic. Beside being specified only for a single source, this method does not consider adaptation to changing proportions between fast and slow traffic rate variations (changing signal/noise ratio) so that it may not be optimal for links serving a large number of sources.
In these two publications, a method is disclosed in which a test is made whether the required bandwidth for a new connection, together with the already allocated bandwidth for existing connections, will exceed a predetermined utilization limit. This limit is dynamically adapted between given minimum and maximum values. The adaptation depends on actual network performance, in particular the fact whether cell losses occurred or not. The method is based on assumed traffic rates and not on the actual traffic situation, and it requires notification of actual cell losses which may cause an undue delay for making correct admission decisions for new connections.
The following publications describe reactive control methods for packet switched networks: